#include <bit/stdc++.h>

using namespace std;

// 到达首都的最少油耗
// 给你一棵 n 个节点的树（一个无向、连通、无环图）
// 每个节点表示一个城市，编号从 0 到 n - 1 ，且恰好有 n - 1 条路
// 0 是首都。给你一个二维整数数组 roads
// 其中 roads[i] = [ai, bi] ，表示城市 ai 和 bi 之间有一条 双向路
// 每个城市里有一个代表，他们都要去首都参加一个会议
// 每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目
// 城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车
// 相邻城市之间一辆车的油耗是一升汽油
// 请你返回到达首都最少需要多少升汽油
// 测试链接 : https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/

class Solution 
{
private:
	// 根据图，当前来到u，u的父节点是fa
	// 遍历完成后，请填好sz[u]、cost[u]
    void f(vector<vector<int>>& g, int seats, int u, int fa, int* sz, long* cost)
    {
        sz[u] = 1;
        for(int v : g[u])
        {
            if(v != fa)
            {
                f(g, seats, v, u, sz, cost);
                sz[u] += sz[v];
                cost[u] += cost[v];
                // a/b向上取整，可以写成(a+b-1)/b
				// (size[v]+seats-1) / seats = size[v] / seats 向上取整
                cost[u] += (sz[v] + seats - 1) / seats;
            }
        }
    }

public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) 
    {
        int n = roads.size() + 1;
        vector<vector<int>> g(n);
        for(auto& r : roads)
        {
            g[r[0]].emplace_back(r[1]);
            g[r[1]].emplace_back(r[0]);
        }
        int sz[n];
        long cost[n];
        memset(sz, 0, sizeof sz);
        memset(cost, 0, sizeof cost);
        f(g, seats, 0, -1, sz, cost);
        return cost[0];
    }
};



class Solution 
{
public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) 
    {
        int n = roads.size() + 1;
        vector<vector<int>> g(n);
        for(auto& e : roads)
        {
            int x = e[0], y = e[1];
            g[x].push_back(y);
            g[y].push_back(x);
        }  

        long long ret = 0;
        function<int(int, int)> dfs = [&](int x, int fa)
        {
            int size = 1;
            for(int y : g[x])
            {
                if(y != fa) size += dfs(y, x);
            }
            if(x != 0) ret += (size + seats - 1) / seats;
            return size;
        };
        dfs(0, -1);

        return ret;
    }
};